#include <unordered_set>
#include <string>
#include <bits/stdc++.h>

using namespace std;

/*
3305. 元音辅音字符串计数 I
已解答
中等
相关标签
相关企业
提示
给你一个字符串 word 和一个 非负 整数 k。

返回 word 的 子字符串 中，每个元音字母（'a'、'e'、'i'、'o'、'u'）至少 出现一次，并且 恰好 包含 k 个辅音字母的子字符串的总数。

 

示例 1：

输入：word = "aeioqq", k = 1

输出：0

解释：

不存在包含所有元音字母的子字符串。

示例 2：

输入：word = "aeiou", k = 0

输出：1

解释：

唯一一个包含所有元音字母且不含辅音字母的子字符串是 word[0..4]，即 "aeiou"。

示例 3：

输入：word = "ieaouqqieaouqq", k = 1

输出：3

解释：

包含所有元音字母并且恰好含有一个辅音字母的子字符串有：

word[0..5]，即 "ieaouq"。
word[6..11]，即 "qieaou"。
word[7..12]，即 "ieaouq"。
 

提示：

5 <= word.length <= 250
word 仅由小写英文字母组成。
0 <= k <= word.length - 5
*/

// 滑动窗口全解

// 法一
/**
 * 使用滑动窗口（Sliding Window）技术来高效地找到符合条件的子字符串。
 * 通过滑动窗口维护一个窗口的状态，包含：
 * 当前窗口中的元音字母。
 * 当前窗口中的辅音字母数量。
 * 当窗口满足条件时，我们统计该窗口的有效子字符串数量。
 */

class Solution {
public:
	int countOfSubstrings(string word, int k) {
		int n = word.size();
		int result = 0;
		// 遍历所有可能的起始点
		for (int left = 0; left < n; ++left) {
			int consonantCount = 0;
			unordered_set<char> vowels;
			// 右边的指针遍历从 left 开始的所有子字符串
			for (int right = left; right < n; ++right) {
				char c = word[right];
				if (isVowel(c)) {
					vowels.insert(c); // 记录元音字母
				} else {
					consonantCount++; // 记录辅音字母
				}
				// 当子字符串长度不满足含有所有元音字母时，跳过
				if (vowels.size() < 5)
					continue;
				// 当辅音字母数量超过 k 时，跳出内层循环
				if (consonantCount > k)
					break;
				// 满足条件，统计有效子字符串
				if (vowels.size() == 5 && consonantCount == k)
					result++;
			}
		}
		return result;
	}

private:
	bool isVowel(char ch) {
		return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
	}
};
	
// 法二
/**
 * 使用滑动窗口（Sliding Window）技术来高效地找到符合条件的子字符串。
 * 通过滑动窗口维护一个窗口的状态，包含：
 * 当前窗口中的元音字母。
 * 当前窗口中的辅音字母数量。
 * 当窗口满足条件时，我们统计该窗口的有效子字符串数量。
 */

class Solution {
	public:
	int countOfSubstrings(string word, int k) {
		unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
		int n = word.size();
		int res = 0;
		for (int i = 0; i < n; ++i) {
			unordered_set<char> occur;
			int consonants = 0;
			bool found = false;
			for (int j = i; j < n; ++j) {
				char c = word[j];
				if (vowels.count(c)) {
					occur.insert(c);
				} else {
					++consonants;
				}
				// 若当前辅音数超过k或条件不满足，且已找到过有效子串，则剪枝
				if (consonants > k) break; 
				if (occur.size() == 5 && consonants == k) {
					++res;
					found = true;
				} else if (found) {
					break; // 后续不再满足条件，提前退出
				}
			}
		}
		return res;
	}
};

// 法三
class Solution {
public:
	// 辅音字母集合（共23个）
	char consonant[23] = "bcdfghjklmnpqrstvwxyz";
	// 记录字符出现频率的数组
	int cnt[128];

	// 检查当前窗口是否符合条件（包含所有元音字母且辅音字母数量 >= k）
	bool check(int k) {
		// 如果所有元音字母的出现次数都大于0
		if (cnt['a'] && cnt['e'] && cnt['i'] && cnt['o'] && cnt['u']) {
			int c = 0;
			// 统计当前窗口中辅音字母的数量
			for(auto s: consonant)
				c += cnt[s];
			// 如果辅音字母的数量大于或等于k，返回true
			return c >= k;
		}
		return false;  // 否则返回false
	}

	// 计算符合条件的子字符串数量
	int countOfSubstrings(string word, int k) {
		int left = 0, right = 0;
		int ans = 0;

		// 第一阶段：计算包含恰好k个辅音字母的符合条件的子字符串
		while (left < word.size()) {
			bool flag = check(k);
			// 右指针扩展，直到窗口符合条件
			while (right < word.size() && !flag) {
				++cnt[word[right++]];  // 增加当前字符的计数
				flag = check(k);  // 检查窗口是否符合条件
			}
			// 如果符合条件，计算所有从当前左指针开始的子字符串
			if (flag) {
				ans += word.size() - right + 1;
			}
			--cnt[word[left++]];  // 收缩左边界，更新计数
		}
		
		// 清空计数器，为第二阶段做准备
		memset(cnt, 0, sizeof(cnt));
		left = right = 0;
		
		// 第二阶段：计算包含恰好k+1个辅音字母的符合条件的子字符串
		while (left < word.size()) {
			bool flag = check(k + 1);
			// 右指针扩展，直到窗口符合条件
			while (right < word.size() && !flag) {
				++cnt[word[right++]];  // 增加当前字符的计数
				flag = check(k + 1);  // 检查窗口是否符合条件
			}
			// 如果符合条件，从结果中减去当前子字符串数目
			if (flag)
				ans -= word.size() - right + 1;
			--cnt[word[left++]];  // 收缩左边界，更新计数
		}

		// 返回结果：符合条件的子字符串数量（恰好包含k个辅音字母）
		return ans;
	}
};